package com.dycong.common.algorithms.fibonacci;

import org.junit.Test;

/**
 * @author dycong
 * @date 2019/4/25 8:29
 */
public class Fibonacci {
    public static long count = 0;

    @Test
    public void libTest() {
        long t = System.currentTimeMillis();
        System.out.println(lib(10) + ":  " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: " + (t = System.currentTimeMillis()));
        System.out.println(lib(20) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: " + (t = System.currentTimeMillis()));
        System.out.println(lib(30) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: " + (t = System.currentTimeMillis()));
        System.out.println(lib(40) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: " + (t = System.currentTimeMillis()));
    }

    private int lib(int i) {
        count++;
        if (i == 1) {
            return 1;
        }
        if (i == 2) {
            return 2;
        }
        return lib(i - 1) + lib(i - 2);
    }


    @Test
    public void dynamicPlanningTest() {
        long t = System.currentTimeMillis();
        System.out.println(dynamicPlanning(10) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: "+(t=System.currentTimeMillis()));
        System.out.println(dynamicPlanning(20) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: "+(t=System.currentTimeMillis()));
        System.out.println(dynamicPlanning(30) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: "+(t=System.currentTimeMillis()));
        System.out.println(dynamicPlanning(40) + ": " + count + ",   exeTime: " + (System.currentTimeMillis() - t) + "     ,cur: "+(t=System.currentTimeMillis()));
    }

    /**
     * 简易的动态规划
     */
    private long dynamicPlanning(int n) {
        long[] cache = new long[n];
        cache[0] = 1;
        cache[1] = 2;
        for (int i = 2; i < n; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
            count++;
        }
        return cache[n - 1];
    }


    /*
    uint32_t f(uint32_t n){

   uint32_t arr[n];

   arr[0]=0;

   arr[1]=1;

   for(uint32_t i=2;i<=n;i++){

       arr[i]=arr[i-1]+arr[i-2];

    }

   return arr[n];

}
     */
}
